#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

//堆排序
void HeapSort(int* arr, int n)
{
	////arr数组直接建堆
	//for (int i = 0; i < n; i++)
	//{
	//	//调用向上调整算法
	//	AdjustUp(arr, i);
	//}
	// 向下调整算法建堆
	for (int i = (n - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}
	 
	 
	
	//排序
	//计算堆尾的位置
	int end = n - 1;
	//当end大于0的时候就说明没有排序完成
	while(end > 0)
	{
		//堆顶的数据和堆尾的数据交换
		Swap(arr, arr + end);
		//此时还不是一个有效的小堆,因此需要向下调整
		AdjustDown(arr, 0, end);
		//元素个数自减
		end--;
	}
}

void HPTest()
{
	//创建堆
	HP hp;
	//初始化堆
	HPInit(&hp);

	//创建数组
	int arr[] = { 17,20,10,13,19,15 };
	//循环6次往堆里面push
	for (int i = 0; i < 6; i++)
	{
		//入堆
		HPPush(&hp, arr[i]);
	}
	//一直取堆顶,直到堆为空跳出循环
	int index = 0;
	while (HPEmpty(&hp))
	{
		////打印堆顶的数据
		//printf("%d ", HPTop(&hp));
		// 
		//取出堆顶的值插入到数组中
		*(arr + index++) = HPTop(&hp);
		//将堆顶的数据出堆
		HPPop(&hp);
	}

	//打印数组
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", *(arr + i));
	}
	printf("\n");

	//销毁堆
	HPDestroy(&hp);
}

void HeapSortTest()
{
	HP hp;
	HPInit(&hp);
	int arr[] = { 17,20,10,13,19,15 };


	HeapSort(arr, 6);

	//打印数组
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", *(arr + i));
	}
	printf("\n");


	HPDestroy(&hp);
}


//造数据
void CreateNDate()
{
	int n = 100000;
	srand(time(0));
	//文件名
	const char* file = "data.txt";
	//以写的形式打开文件
	FILE* fin = fopen(file, "w");
	//判断fopen的返回值
	if (fin == NULL)
	{
		perror("fopen error!\n");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		//生成随机数
		int x = (rand() + i) % 1000000; 
		//写值
		fprintf(fin, "%d\n", x);
	}
	//关闭文件
	fclose(fin);
}

//TOP-K
void TOPk()
{
	int k = 0;
	printf("请输入k:");
	scanf("%d", &k);

	//打开文件
	const char* file = "data.txt";
	FILE* File = fopen(file, "r");
	if (File == NULL)
	{
		perror("fopen fail!\n");
		exit(2);
	}

	//申请k个大小的整型数组
	int* HpMinArr = (int*)malloc(k * sizeof(int));
	if (HpMinArr == NULL)
	{
		perror("malloc fail!\n");
		exit(1);
	}
	
	//取文件中的前k个数据
	for (int i = 0; i < k; i++)
	{
		fscanf(File, "%d", HpMinArr + i);
	}
	//建小堆
	for (int i = (k-1-1)/2; i >= 0; i--)
	{
		//向下调整算法建堆
		AdjustDown(HpMinArr, i, k);
	}
	
	int index = 0;
	//循环读取
	while(fscanf(File, "%d",&index ) != EOF)
	{
		//如果读到的数据比堆顶的数据大就入堆
		if (index > *HpMinArr)
		{
			//入堆
			*HpMinArr = index;
			//向下调整算法使其变成小堆
			AdjustDown(HpMinArr, 0, k);
		}
		
	}
	//打印
	for (int i = 0; i < k; i++)
	{
		printf("%d ", *(HpMinArr + i));
	}
	//关闭文件
	fclose(File);
}

int main()
{
	//HPTest();
	//HeapSortTest();
	//CreateNDate();
	TOPk();
	return 0;
}
